#![allow(dead_code)]
use std::{
    cell::RefCell,
    collections::VecDeque,
    // hash::{Hash, Hasher},
    rc::Rc,
    vec,
};

type TreeLink = Option<Rc<RefCell<TreeNode>>>;

#[derive(Debug)]
struct TreeNode {
    elem: i32,
    left: TreeLink,
    right: TreeLink,
}

// impl Hash for TreeNode {
//     fn hash<H: Hasher>(&self, state: &mut H) {
//         self.hash(state);
//     }
// }

impl TreeNode {
    fn new(elem: i32) -> Self {
        Self {
            elem,
            left: None,
            right: None,
        }
    }
}

fn preorder_recursion(root: &TreeLink, res: &mut Vec<i32>) {
    if root.is_none() {
        return;
    }

    if let Some(node) = root {
        res.push(node.borrow().elem);
        preorder_recursion(&node.borrow().left.clone(), res);
        preorder_recursion(&node.borrow().right.clone(), res);
    }
}

fn preorder_traversal(root: &TreeLink) -> Vec<i32> {
    let mut res: Vec<i32> = Vec::new();
    preorder_recursion(root, &mut res);
    res
}

fn treelink_new(elem: i32) -> TreeLink {
    Some(Rc::new(RefCell::new(TreeNode::new(elem))))
}

fn create_bitree_recursion(node_values: &mut VecDeque<&str>) -> TreeLink {
    let val = node_values.pop_front().unwrap();
    if val == "N" {
        return None;
    }

    let mut node: TreeNode = TreeNode::new(val.parse::<i32>().unwrap());
    node.left = create_bitree_recursion(node_values);
    node.right = create_bitree_recursion(node_values);

    Some(Rc::new(RefCell::new(node)))
}

/* 前序遍历的方式创建二叉树 */
fn create_bitree(s: &str) -> TreeLink {
    let mut node_values: VecDeque<&str> = s.split('_').collect();
    create_bitree_recursion(&mut node_values)
}

fn preorder_traversal2(root: &TreeLink) -> Vec<i32> {
    if root.is_none() {
        return vec![];
    }

    let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![];
    let mut res: Vec<i32> = vec![];

    stack.push(root.clone().unwrap());
    while let Some(cur) = stack.pop() {
        res.push(cur.borrow().elem);
        if let Some(node) = cur.borrow().right.clone() {
            stack.push(node);
        }
        if let Some(node) = cur.borrow().left.clone() {
            stack.push(node)
        }
    }
    res
}

fn inorder_unrecursion(root: &TreeLink) -> Vec<i32> {
    let mut res: Vec<i32> = vec![];
    if root.is_none() {
        return res;
    }

    let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![];
    let mut head = root.clone();
    while !stack.is_empty() || head.is_some() {
        if let Some(node) = head {
            stack.push(node.clone());
            head = node.borrow().left.clone();
        } else {
            if let Some(node) = stack.pop() {
                res.push(node.borrow().elem);
                head = node.borrow().right.clone();
            }
        }
    }

    res
}

fn posorder_unrecursion1(root: &TreeLink) -> Vec<i32> {
    let mut res: Vec<i32> = vec![];
    if root.is_none() {
        return res;
    }

    let mut stack: Vec<TreeLink> = vec![];
    let mut support: Vec<TreeLink> = vec![];
    stack.push(root.clone());
    while !stack.is_empty() {
        if let Some(Some(node)) = stack.pop() {
            support.push(Some(node.clone()));
            stack.push(node.borrow().left.clone());
            stack.push(node.borrow().right.clone());
        }
    }
    while !support.is_empty() {
        if let Some(Some(node)) = support.pop() {
            res.push(node.borrow().elem)
        }
    }

    res
}

fn posorder_unrecursion2(root: &TreeLink) -> Vec<i32> {
    let mut res: Vec<i32> = vec![];
    if root.is_none() {
        return res;
    }

    let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![];
    let mut support: Vec<Rc<RefCell<TreeNode>>> = vec![];
    stack.push(root.clone().unwrap());
    while !stack.is_empty() {
        if let Some(node) = stack.pop() {
            support.push(node.clone());
            if let Some(left_node) = node.borrow().right.clone() {
                stack.push(left_node);
            }
            if let Some(right_node) = node.borrow().left.clone() {
                stack.push(right_node);
            }
        }
    }
    while let Some(node) = support.pop() {
        res.push(node.borrow().elem)
    }

    res
}

fn width_traversial(root: &TreeLink) -> Vec<i32> {
    let mut res: Vec<i32> = vec![];
    let mut queue: VecDeque<TreeLink> = VecDeque::new();

    queue.push_back(root.clone());
    while !queue.is_empty() {
        if let Some(Some(node)) = queue.pop_front() {
            res.push(node.borrow().elem);
            queue.push_back(node.borrow().left.clone());
            queue.push_back(node.borrow().right.clone());
        }
    }

    res
}

pub fn test_tree() {
    // 前序遍历的二叉树
    //let s = "1_2_4_N_N_5_N_N_3_6_N_N_7_N_N";
    let s = "1_2_N_4_6_N_N_7_N_N_3_5_8_N_N_9_N_N_N";
    println!("=======Rc<RefCell<TreeNode>>========");
    let root = create_bitree(s);
    let v = preorder_traversal(&root);
    println!("前序1遍历: {:?}", v);
    let v = preorder_traversal2(&root);
    println!("前序2遍历: {:?}", v);
    let v = inorder_unrecursion(&root);
    println!("中序遍历: {:?}", v);
    let v = posorder_unrecursion1(&root);
    println!("后序1遍历: {:?}", v);
    let v = posorder_unrecursion2(&root);
    println!("后序2遍历: {:?}", v);
    let v = width_traversial(&root);
    println!("宽度遍历: {:?}", v);
}
